<?php
/**
 * @title 211. 添加与搜索单词 - 数据结构设计 - 空间换时间
 * @author start2004
 */

// ini_set("memory_limit", "128M");

class WordDictionary {
    /**
     * Initialize your data structure here.
     */
    function __construct() {
        $this->hashs = [];
        $this->lens = [];
    }

    /**
     * Adds a word into the data structure.
     * @param String $word
     * @return NULL
     */
    function addWord($word) {
        if(!isset($this->hashs[$word])){
            $this->hashs[$word] = 1;

            /**
             * @since 2020-08-17 长度
             */
            $len = strlen($word);
            $this->lens[$len][] = $word;

            /**
             * @since 2020-08-17 首字母
             */
            $this->lens[$word[0]][$len][] = $word;
        } else {}
    }

    /**
     * Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
     * @param String $word
     * @return Boolean
     */
    function search($word) {
        if(strpos($word, ".") !== false){
            /**
             * @since 2020-08-17 存在`.`
             */

            /**
             * @since 2020-08-17 长度
             */
            $len = strlen($word);

            /**
             * @since 2020-08-17 首字母匹配
             */
            if($word[0] == "."){
                if(isset($this->lens[$len])){
                    $words = $this->lens[$len];
                } else {
                    return false;
                }
            } else {
                if(isset($this->lens[$word[0]][$len])){
                    $words = $this->lens[$word[0]][$len];
                } else {
                    return false;
                }
            }

            /**
             * @since 2020-08-17 长度数组中, 硬遍历
             */
            foreach ($words as $w){
                if(self::match($word, $w, $len)){
                    return true;
                    break;
                } else {}
            }

            /**
             * @return
             */
            return false;
        } else {
            return isset($this->hashs[$word]);
        }
    }

    /**
     * @title 字符串匹配
     * @author start2004
     * @since 2020-08-17 Created
     *
     * @param string $word1
     * @param string $word2
     * @param int $len
     * @return bool
     */
    public function match($word1 = "", $word2 = "", $len = 1){
        /**
         * @since 2020-08-17 逐位匹配
         */
        for($i=0; $i<$len; $i++){
            if($word1[$i] !="." AND $word1[$i] != $word2[$i]){
                return false;
            } else {}
        }

        /**
         * @return
         */
        return true;
    }
}



/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.17_5.php
 */
$datas = [
    [
        ["WordDictionary","addWord","addWord","addWord","search","search","search","search"],
        [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]],
    ]
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    $obj = new WordDictionary();

    for ($i=1; $i<count($data[0]); $i++){
        $result = $obj->$data[0][$i]($data[1][$i][0]);

        echo $data[0][$i] ."(\"". $data[1][$i][0] ."\") ";
        if($result === true){
            echo "True";
        } elseif($result === false) {
            echo "False";
        } else {
            echo "Null";
        }
        echo PHP_EOL;
    }

    echo str_repeat(PHP_EOL, 3);
}
$xhprof->end();
